package com.example.offer;

import com.example.structure.TreeNode;

/**
 * 剑指 Offer 28. 对称的二叉树
 * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
 * <p>
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 * <p>
 * 1
 * / \
 * 2   2
 * / \ / \
 * 3  4 4  3
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 * <p>
 * 1
 * / \
 * 2   2
 * \   \
 * 3    3
 */
public class SymmetryTree {
    public boolean isSymmetric(TreeNode root) {
        return root == null || judge(root.left, root.right);
    }

    public boolean judge(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        return judge(left.right, right.left) && judge(left.left, right.right);
    }
}

/**
 * 剑指 Offer 27. 二叉树的镜像
 * 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
 * <p>
 * 例如输入：
 * <p>
 * 4
 * /   \
 * 2     7
 * / \   / \
 * 1   3 6   9
 * 镜像输出：
 * <p>
 * 4
 * /   \
 * 7     2
 * / \   / \
 * 9   6 3   1
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [4,2,7,1,3,6,9]
 * 输出：[4,7,2,9,6,3,1]
 * <p>
 * 思路：递归的拿出当前节点的左右子节点，然后将其调换位置，进行root.left赋值，改变其结构
 */
class MirrorBinaryTree {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

/**
 * 剑指 Offer 26. 树的子结构
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * <p>
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 * <p>
 * 例如:
 * 给定的树 A:
 * <p>
 * 3
 * / \
 * 4   5
 * / \
 * 1   2
 * 给定的树 B：
 * <p>
 * 4
 * /
 * 1
 * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 * <p>
 * 示例 1：
 * <p>
 * 输入：A = [1,2,3], B = [3,1]
 * 输出：false
 */
class isSubStructure {
    /**
     * 变换A的节点值直到找到与B根结点相等的值
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        //判断根节点，再判断左右节点(判断左右节点时等于刷新了根结点，这步时确定A中哪个节点时B的根结点)
        return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    /**
     * 判断以A，B为根结点的两个树是否完全一致
     */
    private boolean isSub(TreeNode A, TreeNode B) {
        //递归终止条件：到达A或B的叶子节点
        //1.如果B为null，说明B都走完了，B都能匹配，返回true
        if (B == null) {
            return true;
        }
        //2.如果A为null，走到这里说明B不为null，则B不能完全匹配，返回false
        //3.A的值与B的值不同，返回false（2与3合并）
        if (A == null || A.val != B.val) {
            return false;
        }
        //走到这里说明A的值与B的值相等，递归各自的左右节点
        return isSub(A.left, B.left) && isSub(A.right, B.right);
    }
}
